Analyse numérique et réduction de réseaux
Identifieur interne : 002F94 ( Main/Exploration ); précédent : 002F93; suivant : 002F95Analyse numérique et réduction de réseaux
Auteurs : Ivan Morel [Australie, France] ; Damien Stehlé [Australie] ; Gilles Villard [France]Source :
- Technique et Science Informatiques [ 0752-4072 ] ; 2010.
Abstract
L’algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu ’il est donc important de rendre aussi efficace que possible. Une approche initiée par Schnorr consiste à effectuer des calculs approchés pour estimer les orthogonalisations de Gram-Schmidt sous-jacentes. Sans approximations, ces calculs dominent le coût de la réduction. Récemment, des outils classiques d’analyse numérique ont été revisités et améliorés, pour exploiter plus systématiquement l’idée de Schnorr et réduire les coûts. Nous décrivons ces développements, notamment comment l’algorithmique en nombres flottants peut être introduite à plusieurs niveaux dans la réduction.
The algorithmic facet of euclidean lattices is a frequent tool in computer science and mathematics. It mainly relies on the LLL reduction, making worthwile efficiency improvements. Schnorr proved that the LLL algorithm can be speeded up if one computes approximations to the underlying Gram-Schmidt orthogonalisations. Without approximations, these computations dominate the cost of the reduction. Recently, classical tools from the field of numerical analysis have been revisited and improved in order to strengthen Schnorr’s approach, and further reducing the costs. We describe these developments, and show especially how floating-point computations may be introduced at various levels in the reduction process.
Url:
DOI: 10.3166/tsi.29.115-144
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000067
- to stream Istex, to step Curation: 000067
- to stream Istex, to step Checkpoint: 000756
- to stream Main, to step Merge: 003051
- to stream Main, to step Curation: 002F94
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="fr">Analyse numérique et réduction de réseaux</title><author><name sortKey="Morel, Ivan" sort="Morel, Ivan" uniqKey="Morel I" first="Ivan" last="Morel">Ivan Morel</name></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name></author><author><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:0320CAA363024371D91378945C693F60C2588974</idno><date when="2010" year="2010">2010</date><idno type="doi">10.3166/tsi.29.115-144</idno><idno type="url">https://api.istex.fr/ark:/67375/HT0-21FTRL8V-H/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000067</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000067</idno><idno type="wicri:Area/Istex/Curation">000067</idno><idno type="wicri:Area/Istex/Checkpoint">000756</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000756</idno><idno type="wicri:doubleKey">0752-4072:2010:Morel I:analyse:numerique:et</idno><idno type="wicri:Area/Main/Merge">003051</idno><idno type="wicri:Area/Main/Curation">002F94</idno><idno type="wicri:Area/Main/Exploration">002F94</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="fr">Analyse numérique et réduction de réseaux</title><author><name sortKey="Morel, Ivan" sort="Morel, Ivan" uniqKey="Morel I" first="Ivan" last="Morel">Ivan Morel</name><affiliation wicri:level="3"><country>Australie</country><placeName><settlement type="city">Sydney</settlement><region type="état">Nouvelle-Galles du Sud</region></placeName><wicri:orgArea>Université de Lyon, ÉNS de Lyon</wicri:orgArea></affiliation><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>INRIA, Laboratoire LIP, 46 Allée d’Italie69364Lyon cedex 07</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">cedex 07</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author><author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>CNRS, Universités de Sydney et Macquarie Département de Mathématiques et de Statistiques (F07), Université de SydneyNSW2006</wicri:regionArea><wicri:noRegion>Université de SydneyNSW2006</wicri:noRegion></affiliation><affiliation></affiliation></author><author><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>INRIA, Laboratoire LIP, 46 Allée d’Italie69364Lyon cedex 07</wicri:regionArea><placeName><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region><settlement type="city">cedex 07</settlement></placeName></affiliation><affiliation wicri:level="3"><country>France</country><placeName><settlement type="city">Lyon</settlement><region type="region" nuts="2">Auvergne-Rhône-Alpes</region><region type="old region" nuts="2">Rhône-Alpes</region></placeName><wicri:orgArea>CNRS, Université de Lyon</wicri:orgArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">France</country></affiliation></author></analytic><monogr></monogr><series><title level="j" type="main">Technique et Science Informatiques</title><title level="j" type="abbrev">Tech. Sci. Info.</title><idno type="ISSN">0752-4072</idno><idno type="eISSN">2116-5920</idno><imprint><publisher>Lavoisier</publisher><date type="published" when="2010-01">2010</date><biblScope unit="vol">29</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="115">115</biblScope><biblScope unit="page" to="144">144</biblScope><biblScope unit="page-count">30</biblScope><biblScope unit="ref-count">0</biblScope><biblScope unit="fig-count">0</biblScope><biblScope unit="table-count">0</biblScope></imprint><idno type="ISSN">0752-4072</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0752-4072</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="fr">L’algorithmique des réseaux euclidiens est un outil fréquemment utilisé en informatique et en mathématiques. Elle repose essentiellement sur la réduction LLL qu ’il est donc important de rendre aussi efficace que possible. Une approche initiée par Schnorr consiste à effectuer des calculs approchés pour estimer les orthogonalisations de Gram-Schmidt sous-jacentes. Sans approximations, ces calculs dominent le coût de la réduction. Récemment, des outils classiques d’analyse numérique ont été revisités et améliorés, pour exploiter plus systématiquement l’idée de Schnorr et réduire les coûts. Nous décrivons ces développements, notamment comment l’algorithmique en nombres flottants peut être introduite à plusieurs niveaux dans la réduction.</div><div type="abstract" xml:lang="en">The algorithmic facet of euclidean lattices is a frequent tool in computer science and mathematics. It mainly relies on the LLL reduction, making worthwile efficiency improvements. Schnorr proved that the LLL algorithm can be speeded up if one computes approximations to the underlying Gram-Schmidt orthogonalisations. Without approximations, these computations dominate the cost of the reduction. Recently, classical tools from the field of numerical analysis have been revisited and improved in order to strengthen Schnorr’s approach, and further reducing the costs. We describe these developments, and show especially how floating-point computations may be introduced at various levels in the reduction process.</div></front></TEI><affiliations><list><country><li>Australie</li><li>France</li></country><region><li>Auvergne-Rhône-Alpes</li><li>Nouvelle-Galles du Sud</li><li>Rhône-Alpes</li></region><settlement><li>Lyon</li><li>Sydney</li><li>cedex 07</li></settlement></list><tree><country name="Australie"><region name="Nouvelle-Galles du Sud"><name sortKey="Morel, Ivan" sort="Morel, Ivan" uniqKey="Morel I" first="Ivan" last="Morel">Ivan Morel</name></region><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name></country><country name="France"><region name="Auvergne-Rhône-Alpes"><name sortKey="Morel, Ivan" sort="Morel, Ivan" uniqKey="Morel I" first="Ivan" last="Morel">Ivan Morel</name></region><name sortKey="Morel, Ivan" sort="Morel, Ivan" uniqKey="Morel I" first="Ivan" last="Morel">Ivan Morel</name><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name><name sortKey="Villard, Gilles" sort="Villard, Gilles" uniqKey="Villard G" first="Gilles" last="Villard">Gilles Villard</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002F94 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002F94 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:0320CAA363024371D91378945C693F60C2588974
|texte= Analyse numérique et réduction de réseaux
}}
| This area was generated with Dilib version V0.6.33. |  |